// https://gitee.com/douma_edu/douma_algo_training_camp/issues/I4KWJK
// 题目类似 力扣 132模式这道题。可以两个都看看，132较难
package main

import "fmt"

func GetValue(nums []int) []int {
	// 1. 首先求出比左边都大的元素索引
	// 维护一个变量 maxLeft
	maxLeft := nums[0]
	// 定义一个集合存储这些(go 集合不记得咋表示了，用map一样)
	maxLeftMap := make(map[int]bool)
	for i := 1; i < len(nums)-1; i++ {
		if nums[i] > maxLeft {
			maxLeftMap[i] = true
			// 更新左边最大值
			maxLeft = nums[i]
		}
	}

	// 2. 同理最简单的方法是，求出比右边都小的都可以是谁
	// 求得同时进行判断，是否左边也满足，满足就返回索引
	rst := make([]int, 0)
	minRight := nums[len(nums)-1]
	for i := len(nums) - 1; i > 0; i-- {
		if nums[i] < minRight {
			// 判断左边是否同样满足
			if maxLeftMap[i] {
				rst = append(rst, i)
			}
			// 更新右边最小值
			minRight = nums[i]
		}
	}
	return rst
}

func GetValue2(nums []int) []int {
	n := len(nums)
	// 维护一个 maxLeft
	maxLeft := nums[0]
	stack := make([]int, 0)
	for i := 1; i < n; i++ {
		// 1. 满足 “最大”入栈, 对 i 要求是 1 到 n-1
		if nums[i] > maxLeft && i < n-1 {
			stack = append(stack, i)
			maxLeft = nums[i]
			continue
		}
		// 2. 否则它必然小于栈中的 某些  “最大”数
		// 使最大数不能满足成为 “最小”， 那么出栈
		for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
			stack = stack[:len(stack)-1]
		}
	}
	return stack
}

func main() {
	nums := []int{1, 2, 1, 3, 5, 8}
	nums = []int{1, 2, 1, 3, 5, 4}
	rst := GetValue2(nums)
	fmt.Println(rst)
}
